package com.learning.recursive;

import java.io.PrintStream;

/**
 * queen backtracking
 * 
 * @author AnND1
 * 
 */
public class Queen {
	// initial
	private final boolean available = true;
	private final int squares = 6, norm = squares - 1;
	private int[] positionInRow = new int[squares];
	private boolean[] column = new boolean[squares];
	private boolean[] leftDiagonal = new boolean[squares * 2 - 1];
	private boolean[] rightDiagonal = new boolean[squares * 2 - 1];
	private int howMany = 0;
	int a[][] = new int[squares][squares];

	public Queen() {
		for (int i = 0; i < squares; i++) {
			positionInRow[i] = -1;
			column[i] = available;
		}
		for (int i = 0; i < squares; i++) {
			for (int j = 0; j < squares; j++)
				a[i][j] = 0;
		}
		for (int i = 0; i < squares * 2 - 1; i++)
			leftDiagonal[i] = rightDiagonal[i] = available;
	}

	public void PrintBoard(int a[][]) {
		// left for exercise;
		for (int i = 0; i < squares; i++) {
			for (int j = 0; j < squares; j++)
				System.out.print(a[i][j] + "\t");
			System.out.print("\n");
		}
	}

	public void PutQueen(int row) {
		for (int col = 0; col < squares; col++)
			if (column[col] == available
					&& leftDiagonal[row + col] == available
					&& rightDiagonal[row - col + norm] == available) {
				positionInRow[row] = col;
				a[row][col] = 1;
				column[col] = !available;
				leftDiagonal[row + col] = !available;
				rightDiagonal[row - col + norm] = !available;
				if (row < squares - 1)
					PutQueen(row + 1);
				else {
					PrintBoard(a);
					System.out.println("======================================================");
					howMany++;
				}
				a[row][col] = 0;
				column[col] = available;
				leftDiagonal[row + col] = available;
				rightDiagonal[row - col + norm] = available;
			}
	}

	public static void main(String args[]) {
		Queen queen = new Queen();
		queen.PutQueen(0);
		System.out.println(queen.howMany + " solutions found.");
	}
}
